package 中等.贪心思想;

/**
 * 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
 * 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油
 * 站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
 * 给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回
 * 出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/gas-station
 */
public class 加油站_134 {

    public static void main(String[] args) {

        int[] gas = {2, 3, 4,};
        int[] cost = {3, 4, 3};
        System.out.println(canCompleteCircuit(gas, cost));

    }

    /**
     * 贪心思想：
     * 如果从起点x到达不了y的位置，那么x与y中间的位置也到达不了y的位置
     * 例如从x+1作为起点，那么又是从0开始，而x->x+1或许有剩下的油，有剩下
     * 的油的都到达不了y的位置，那么x+1更不可能到达
     */
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int cur = 0;
        while (cur < gas.length) {
            if (gas[cur] < cost[cur]) {  //起点加的油不够到下一个加油站
                cur++;
                continue;
            }
            int extraCost = 0;  //用来记录剩下的油
            for (int right = cur; right < gas.length; right++) {
                extraCost += gas[right] - cost[right];
                if (extraCost < 0) {
                    cur = right;
                    break;
                }
            }
            if (extraCost < 0) {  //大于0说明已经遍历到了第length-1个加油站
                continue;
            }
            for (int left = 0; left < cur; left++) {  //需要加上前面的加油站连成环
                extraCost += gas[left] - cost[left];
                if (extraCost < 0) {  //例如总共有4个加油站，2遍历到了4还有剩余油，需要到达第1个加油站，连成环
                    return -1;  //当2到达不了1时，那么从2-4的所有加油站都到达不了1，直接无法行使一周
                }
            }
            return cur;
        }
        return -1;
    }

}
